package com.algorithm.treenode;

import com.dataconsruct.TreeNode;
import com.google.common.collect.Lists;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;


/**
 * 二叉树层序遍历，即广度遍历
 */
public class LevelOrderTest {
    public static void main(String[] args) {
        TreeNode leafTreeNode4 = new TreeNode(4);
        TreeNode leafTreeNode5 = new TreeNode(5);
        TreeNode leafTreeNode6 = new TreeNode(6);
        TreeNode leafTreeNode7 = new TreeNode(7);
        TreeNode treeNode2 = new TreeNode(2, leafTreeNode4, leafTreeNode5);
        TreeNode treeNode3 = new TreeNode(3, leafTreeNode6, leafTreeNode7);
        TreeNode root = new TreeNode(1, treeNode2, treeNode3);

        // 第一种方式
        new LevelOrderTest().printCurrentNodesAndTheirChildren(Lists.newArrayList(root));

        System.out.println("-------------分割线-------------");
        // 第二种方式
        new LevelOrderTest().levelOrder(root).forEach(System.out::println);
    }

    /*
     * 简单粗暴的层序遍历：
     *      每次传入当前层的节点列表，打印当前层节点值，并将下一层节点加入列表，递归调用
     */
    public void printCurrentNodesAndTheirChildren(List<TreeNode> treeNodeList) {
        if (treeNodeList == null || treeNodeList.isEmpty())
            return;

        List<TreeNode> nodeArrayList = new ArrayList<>();
        for (TreeNode treeNode : treeNodeList) {
            System.out.println(treeNode.val);
            if (treeNode.left != null) {
                nodeArrayList.add(treeNode.left);
            }
            if (treeNode.right != null) {
                nodeArrayList.add(treeNode.right);
            }
        }

        printCurrentNodesAndTheirChildren(nodeArrayList);
    }

    /**
     * 利用队列先进先出的特性：
     *      存当前节点值，并把左右节点加入队列，不断从队列中取节点处理，知道队列为空
     */
    List<Integer> levelOrder(TreeNode root) {
        ArrayList<Integer> result = new ArrayList<>();
        Queue<TreeNode> queue = new LinkedList<>();

        queue.add(root);

        while (!queue.isEmpty()) {
            TreeNode pollNode = queue.poll();
            if (pollNode != null) {
                result.add(pollNode.val);
                if (pollNode.left != null)
                    queue.offer(pollNode.left);
                if (pollNode.right != null)
                    queue.offer(pollNode.right);
            }
        }
        return result;
    }
}
